package org.example.everyday;

import org.example.ch04.tree.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/6/19 0019 10:11
 */
public class Lc508 {
    HashMap<Integer, Integer> map = new HashMap<>();
    int maxFreq = 0;
    public static void main(String[] args) {
        Lc508 lc508 = new Lc508();

//        root = [5,2,-3]

        TreeNode leftNode = new TreeNode(2);
        TreeNode rightNode = new TreeNode(-3);
        TreeNode root = new TreeNode(5,leftNode,rightNode);
        int[] res = lc508.findFrequentTreeSum(root);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }


    }

    public int[] findFrequentTreeSum(TreeNode root){
        postOrder(root);
        List<Integer> ans = new ArrayList<>();
        for (Integer num : map.keySet()){
            if(map.get(num) == maxFreq){
                ans.add(num);
            }
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    public int postOrder(TreeNode root){
        if(root == null)
            return 0;

        int leftSum  = postOrder(root.left);
        int rightSum = postOrder(root.right);

        int val = root.val + leftSum + rightSum;
        map.put(val, map.getOrDefault(val, 0) + 1);
        maxFreq = Math.max(maxFreq, map.get(val));

        return val;
    }



}
